"""
https://leetcode.cn/problems/decode-string/description/

394. 字符串解码
TODO 待完成
已解答
中等
相关标签
premium lock icon
相关企业
给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

 

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
 

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300] 

"""

from typing import List


class Solution:
    """
    本题难点在于处理括号包含括号的情况。
    很容易想到使用栈去处理这种情况。

    处理数字：堆入栈中
    处理[：判断有无对应数字，如果没有，则默认1
    处理]：阶段性收尾

    另一种思路是，遍历获取所有中括号的索引。
    必定有一个前括号就对应一个后括号。

    处理时，按照后括号的顺序处理字符串。

    """

    def decodeString(self, s: str) -> str:
        def is_num(c:str)->bool:
            return ord('0')<=ord(c)<=ord('9')
        def is_letter(c:str)->bool:
            return ord('a')<=ord(c)<=ord('z')
        
        def calc_char_type(c:str)->int:
            if c=='[' or c==']':
                return c
            if is_num(c):
                return 'n'
            else:
                return 'l'
        
        times_stack=[]
        str_stack=[]
        recent_idx=0
        last_type=None
        for i,ch in enumerate(s):
            cur_type=calc_char_type(ch)
            if not last_type :
                last_type=cur_type
                continue
            if last_type==cur_type:
                continue
            if last_type=='n':
                times_stack.append(int(s[recent_idx:i]))
            if last_type=='l':
                str_stack.append(s[recent_idx:i])

                
            if cur_type==']':
                last_str=str_stack.pop()
                last_times=times_stack.pop()
                str_stack.append((str_stack.pop() if str_stack else '')+last_str*last_times)

            recent_idx=i
            last_type=cur_type

        last_str=str_stack.pop()
        last_times=times_stack.pop()
        str_stack.append((str_stack.pop() if str_stack else '')+last_str*last_times)
        
        return str_stack[-1]

if __name__=='__main__':
    """
    3[a]2[bc]
    aaa2[bc]
    aaabcbc

    3[a2[c]]
    3   2
    a   c
    3[acc]
    accaccacc

    2[abc]3[cd]ef
    abcabc3[cd]ef
    abcabccdcdcdef

    从上面的解析中可得，每次遇到后半括号，都是一次结算。
    结算的过程，是将上一次数字出现的位置到本次]出现的位置，转换为实际字符串。
    同时需要将之前的信息保存到栈中。包括：倍率栈，字符串栈。两个栈的索引是对应关系。

    """
    s='3[a]2[bc]'

    sol=Solution()
    res=sol.decodeString(s)
    print(res)



